package problems;

import java.math.BigInteger;

import org.junit.Ignore;

/**
 * If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
 * {20,48,52}, {24,45,51}, {30,40,50}
 * For which value of p ≤ 1000, is the number of solutions maximised?
 * @author laszlo
 */
@Ignore //threaded is 50% faster
public class Euler039 extends AbstractEuler {

	@Override
	/**
	 * Any solution will satisfy the pythagorean formula, a^2 + b^2 = c^2, where a, b and c are the side lengths.
	 * Calculating if this holds is nearly trivial; the real exercise is in dividing 1 <= n <= 1000 into three
	 * parts.
	 * 
	 * Possible optimizations include looking into Pythagorean triples: http://mathworld.wolfram.com/PythagoreanTriple.html
	 */
	public Number calculate() {
		int maxNumSolutions = 1;
		int maxNumSolutionsFor = 3 + 4 + 5; //the golden cut is the lower bound - there can be only one solution here
		
		/*
		From rayfil in the forums:
		
		If both a and b are even, c will also be even and P (the perimeter) will be even.
		If both a and b are odd, c will be even and P will be even.
		If one is even and the other is odd, c will be odd and P will again be even.
		Therefore, only even values of P need to be checked.
		*/ 
		
		for (int i = maxNumSolutionsFor + 2; i <= 1000; i += 2) {
			int foundSolutions = 0;
			for (int c = i; c >= i / 3; c--) {
				for (int b = i - c; b >= (i - c) / 2; b--) {
					int a = i - (b + c);
					if (a == 0 || b == 0 || c == 0) continue;
					if (doesPythagorasHold(a, b, c)) {
						foundSolutions++;
					}
				}
			}
			if (foundSolutions > maxNumSolutions) {
//				System.out.println(i + " has " + foundSolutions + " solutions");
				maxNumSolutions = foundSolutions;
				maxNumSolutionsFor = i;
			}
		}
		return maxNumSolutionsFor;
	}
	
	private boolean doesPythagorasHold(int a, int b, int c) {
		if (a <= 0 || b <= 0 || c <= 0) throw new UnsupportedOperationException("only positive values");
		return BigInteger.valueOf(a).pow(2).add(BigInteger.valueOf(b).pow(2)).equals(BigInteger.valueOf(c).pow(2));
	}
	
	public void testPythagoras() {
		assertTrue("3,4,5 fails", doesPythagorasHold(3, 4, 5));
		assertTrue("30,40,50 fails", doesPythagorasHold(30, 40, 50));
		assertFalse("2,3,4 passes", doesPythagorasHold(2, 3, 4));
		assertFalse("10,1,1 passes", doesPythagorasHold(10, 1, 1));
		try {
			assertFalse("10,0,0 passes", doesPythagorasHold(10, 0, 0));
			assertFalse("10,0,1 passes", doesPythagorasHold(10, 0, 1));
			assertFalse("10,1,0 passes", doesPythagorasHold(10, 1, 0));
			assertFalse("0,0,0 passes", doesPythagorasHold(0, 0, 0));
			fail ("0 passes");
		} catch (UnsupportedOperationException e) {
			//ok
		}
	}

	@Override
	protected Number getCorrectAnswer() {
		return 840;
	}

}
